'''
希尔排序
分组插入排序算法

'''

# 插入排序改编
def insert_sort_gap(li, gap):  # gap分的组
    for i in range(gap, len(li)):  # i 表示摸到的牌的下标
        tmp = li[i]
        j = i - gap  # j指的是手里牌的下标
        while j >= 0 and li[j] > tmp:
            li[j + gap] = li[j]
            j -= gap
        li[j + gap] = tmp


def shell_sort(li):
    d = len(li) // 2
    while d >= 1:  # 直到d=1结束
        insert_sort_gap(li, d)
        d //= 2


import random

li = list(range(1000))
random.shuffle(li)

shell_sort(li)
print(li)
